// @algorithm @lc id=45 lang=cpp 
// @title jump-game-ii


// #define print(...)
// @test([2,3,1,1,4])=2
// @test([2,3,0,1,4])=2
// @test([2,1,1,1,1])=3
class Solution {
public:
    int jump(vector<int>& nums) {
        int jump = 0/*下一跳的索引*/, nextJump = 0, step = 0/*跳跃次数*/;
        for(int i=0; i<nums.size()-1; i++){
            nextJump = max(nextJump, i+nums[i]);
            if(i==jump){
                step++;
                jump = nextJump;
            }
        }
        return step;
    }
};